const tree = {
  val: "a",
  children: [
    { val: "a-1", children: [{ val: "a-1-1", children: null }] },
    { val: "a-2", children: [{ val: "a-2-1", children: null }] },
  ],
};

/**
 * 深度优先遍历：尽可能深的搜索树的分支
 * children 递归遍历
 */
const dfs = (root) => {
  console.log(root.val); // a a-1 a-1-1 a-2 a-2-1
  root?.children.forEach((e) => {
    dfs(e);
  });
};
// dfs(tree);

// 广度优先遍历：先访问离根节点最近的节点
const bfs = (root) => {
  const q = Array.isArray(root) ? JSON.parse(JSON.stringify(root)) : [root]; // 队列
  while (q.length) {
    const p = q.shift(); // 队头出队，删除第一项并返回
    console.log(p.val); // a a-1 a-2 a-1-1 a-2-1
    p?.children.forEach((e) => {
      q.push(e);
    });
  }
};
bfs(tree);
console.log("tree", tree);
